'''
Created on Jul 21, 2011

@author: anupams
'''

from com.anupam.graphs.GraphsAnupam import SampleGraphObject

class CycleDetection(object):
  """
    Class for detecting a cyclic graph.
  """

  def __init__(self,graphDict, nodes):
    """
    Default constructor of the class.
    
    Args:
      graphDict : Adjucancy list of the graph
      nodes : graph node objects @see{ColoredGraphNode}
    """
    self.graphDict = graphDict
    self.nodes = nodes
    ## Container for storing nodes that are being checked for a cycle.
    self.traversednodes = []
    ## Flag indicatng that recursive calls must be stopped and as a cycle has been detected.
    self.breakRecursion = False

  def __clearState(self):
    self.breakRecursion= False
    del(self.traversednodes[:])

  def checkUnprocessedNodes(self):
    """
      Iterates over the nodes of the graph and checks if any 
      node is white in color and uses that node
    """
    self.__clearState()
    for key in self.nodes:
      nodeObj = self.nodes[key]
      if not self.breakRecursion: 
        if nodeObj.color == 'white':
          self.__detectCycle(key)
        else:
          continue
      else:
        return self.traversednodes

  def __checkAndInsert(self,nodeName):
    """
      Checks if the node is already traversed.
      nodeName : Node to be checked
    """
    try:
      if self.traversednodes.index(nodeName):
        return -1
    except ValueError:
      self.traversednodes.append(nodeName)
      pass

  def __detectCycle(self,nodeName):
    """
      Checks if a graph is cyclic.
    """
    nodeObj = self.nodes[nodeName]
    nodeObj.color = 'grey'

    adjucancyList = self.graphDict[nodeName]
    copyOfAdjucancyList = list(adjucancyList)

    if self.__checkAndInsert(nodeName) == -1:
      self.traversednodes.append(nodeName)
      print 'Cycle detected in graph :: '
      print str(self.traversednodes)
      self.breakRecursion = True
      return

    if not self.breakRecursion:
      while len(copyOfAdjucancyList):
        childNodeName = copyOfAdjucancyList.pop(0)
        self.__detectCycle(childNodeName)
        if self.breakRecursion:
          return


if __name__ == '__main__':
  directedGraphSample = SampleGraphObject()
  graphDict = directedGraphSample.directedGraphSample()
  traverse = CycleDetection(graphDict, directedGraphSample.nodes)
  traverse.checkUnprocessedNodes()
